Smallest string starting from leaf [DFS]¶
Time: O(N+LxH); Space: O(H); medium
Given the root of a binary tree, each node has a value from 0 to 25 representing the letters ‘a’ to ‘z’: a value of 0 represents ‘a’, a value of 1 represents ‘b’, and so on.
Find the lexicographically smallest string that starts at a leaf of this tree and ends at the root.
(As a reminder, any shorter prefix of a string is lexicographically smaller: for example, “ab” is lexicographically smaller than “aba”. A leaf of a node is a node that has no children.)
Example 1:
Input: root = {TreeNode} [0,1,2,3,4,3,4]
Output: “dba”
Example 2:
Input: root = {TreeNode} [25,1,3,1,3,0,2]
Output: “adz”
Example 3:
Input: root = {TreeNode} [2,2,1,null,1,0,null,0]
Output: “abc”
Constraints:
The number of nodes in the given tree will be between 1 and 8500.
Each node in the tree will have a value between 0 and 25.
[1]:
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
1. Depth First Search¶
[2]:
class Solution1(object):
"""
Time: O(N+L*H), L is the number of leaves
Space: O(H)
"""
def smallestFromLeaf(self, root):
"""
:type root: TreeNode
:rtype: str
"""
def dfs(node, candidate, result):
if not node:
return
candidate.append(chr(ord('a') + node.val))
if not node.left and not node.right:
result[0] = min(result[0], ''.join(reversed(candidate)))
dfs(node.left, candidate, result)
dfs(node.right, candidate, result)
candidate.pop()
result = ["~"]
dfs(root, [], result)
return result[0]
[3]:
s = Solution1()
# [0,1,2,3,4,3,4]
root = TreeNode(0)
root.left, root.right = TreeNode(1), TreeNode(2)
root.left.left, root.left.right = TreeNode(3), TreeNode(4)
root.right.left, root.right.right = TreeNode(3), TreeNode(4)
assert s.smallestFromLeaf(root) == "dba"
# [25,1,3,1,3,0,2]
root = TreeNode(25)
root.left, root.right = TreeNode(1), TreeNode(3)
root.left.left, root.left.right = TreeNode(1), TreeNode(3)
root.right.left, root.right.right = TreeNode(0), TreeNode(2)
assert s.smallestFromLeaf(root) == "adz"
# [2,2,1,null,1,0,null,0]
root = TreeNode(2)
root.left, root.right = TreeNode(2), TreeNode(1)
root.left.right = TreeNode(1)
root.right.left = TreeNode(0)
root.left.right.left = TreeNode(0)
assert s.smallestFromLeaf(root) == "abc"